package code.BinaryTree;

import struct.LinkList;
import struct.Tree;
import struct.TreeNode;

import java.util.*;

public class PathSum {
	Map<TreeNode, TreeNode> parent;

	public static void main(String[] args) {
		TreeNode tree = Tree.constructTree("[5,4,8,11,null,13,4,7,2,null,null,5,1]");
		PathSum pathSum = new PathSum();
		System.out.print("124.二叉树中的最大路径和:");
		int sum = pathSum.maxPathSum(tree);
		System.out.println(sum);

		System.out.print("在二叉树中找到累加和为指定值得最长路径:");
		int maxLength = pathSum.getMaxLength(tree, 22);
		System.out.println(maxLength);

		System.out.print("112. 路径总和:");
		boolean has = pathSum.hasPathSum(tree, 1);
		System.out.println(has);

		System.out.print("113. 路径总和 II:");
		List<List<Integer>> lists = pathSum.pathSumII(tree, 22);
		System.out.println(lists);

		System.out.print("437. 路径总和 III:\n");
		tree = Tree.constructTree("[10,5,-3,3,2,null,11,3,-2,null,1]");
		int nums = pathSum.pathSumIII(tree, 8);
		System.out.println("\t\t" + nums);
		int pathSumIII2 = pathSum.pathSumIII2(tree, 8);
		System.out.println("\t\t" + pathSumIII2);

		System.out.print("129. 求根到叶子节点数字之和:");
		tree = Tree.constructTree("[4,9,0,5,1]");
		int sumNumbers = pathSum.sumNumbers(tree);
		System.out.println("\t\t" + sumNumbers);

		System.out.print("543. 二叉树的直径");
		tree = Tree.constructTree("[1,2,3,4,5]");
		int i = pathSum.diameterOfBinaryTree(tree);
		System.out.println("\t\t" + i);

		System.out.print("687. 最长同值路径:");
		tree = Tree.constructTree("[1,4,5,4,4,null,5]");
		int longestUnivaluePath = pathSum.longestUnivaluePath(tree);
		System.out.println(longestUnivaluePath);


		System.out.print("863. 二叉树中所有距离为 K 的结点");
		TreeNode treeNode = Tree.constructTree("[3,5,1,6,2,0,8,null,null,7,4]");
		List<Integer> integers = pathSum.distanceK(treeNode, treeNode.left, 2);
		System.out.println(integers);
	}

	//124.二叉树中的最大路径和
	public int maxPathSum(TreeNode root) {
		int[] maxSum = new int[1];
		maxSum[0] = Integer.MIN_VALUE;
		maxPathSumHelper(root, maxSum);
		return maxSum[0];
	}

	//124.二叉树中的最大路径和-辅助函数
	public int maxPathSumHelper(TreeNode root, int[] maxSum) {
		if (root == null) {
			return 0;
		}
		int lSum = Math.max(maxPathSumHelper(root.left, maxSum), 0);//移除比较代码 lSum<0
		int rSum = Math.max(maxPathSumHelper(root.right, maxSum), 0);//移除比较代码 rSum<0
		int aSum = root.val + lSum + rSum;//直接使用 root.val，少了创建一个临时变量
		maxSum[0] = Math.max(aSum, maxSum[0]);
		return root.val + Math.max(rSum, lSum);
	}

	// 在二叉树中找到累加和为指定值的最长路径
	public int getMaxLength(TreeNode root, int sum) {
		if (root == null) {
			return 0;
		}
		HashMap<Integer, Integer> hashMap = new HashMap<>();
		hashMap.put(0, 0);
		return getMaxLengthHelper(root, hashMap, sum, 0, 1, 0);
	}

	// 在二叉树中找到累加和为指定值得最长路径-辅助函数
	public int getMaxLengthHelper(TreeNode root, HashMap<Integer, Integer> hashMap, int sum, int preSum, int level, int maxLength) {
		if (root == null) {
			return maxLength;
		}
		int curSum = preSum + root.val;
		if (!hashMap.containsKey(curSum)) {
			hashMap.put(curSum, level);
		}
		if (hashMap.containsKey(curSum - sum)) {
			maxLength = Math.max(maxLength, level - hashMap.get(curSum - sum));
		}
		maxLength = getMaxLengthHelper(root.left, hashMap, sum, curSum, level + 1, maxLength);
		maxLength = getMaxLengthHelper(root.right, hashMap, sum, curSum, level + 1, maxLength);
		hashMap.remove(curSum);
		return maxLength;
	}

	//112. 路径总和
	public boolean hasPathSum(TreeNode root, int sum) {
		if (root == null) {
			return false;
		}
		int curVal = root.val;
		if (sum == curVal && root.left == null && root.right == null) {
			return true;
		}
		boolean lHas = hasPathSum(root.left, sum - curVal);
		boolean rHas = hasPathSum(root.right, sum - curVal);

		return lHas || rHas;
	}

	//	113. 路径总和 II
	public List<List<Integer>> pathSumII(TreeNode root, int sum) {
		List<List<Integer>> lists = new ArrayList<>();
		pathSumIIHelper(root, lists, sum, new ArrayList<Integer>());
		return lists;
	}

	public void pathSumIIHelper(TreeNode head, List<List<Integer>> lists, int sum, List<Integer> list) {
		if (head == null) {
			return;
		}
		list.add(head.val);
		if (head.val == sum && head.left == null && head.right == null) {
			lists.add(new ArrayList<>(list));
		}
		pathSumIIHelper(head.left, lists, sum - head.val, list);
		pathSumIIHelper(head.right, lists, sum - head.val, list);
		list.remove(list.size() - 1);
	}

	//437. 路径总和 III
	public int pathSumIII(TreeNode root, int sum) {
		if (root == null) {
			return 0;
		}
		int[] arrs = new int[1];
		pathSumIIIHelper(root, sum, arrs);
		return arrs[0] + pathSumIII(root.left, sum) + pathSumIII(root.right, sum);
	}

	public void pathSumIIIHelper(TreeNode root, int sum, int[] arrs) {
		if (root == null) {
			return;
		}
		if (root.val == sum) {
			arrs[0]++;
		}
		pathSumIIIHelper(root.left, sum - root.val, arrs);
		pathSumIIIHelper(root.right, sum - root.val, arrs);
	}

	//437. 路径总和 III 2
	public int pathSumIII2(TreeNode root, int sum) {
		if (root == null) {
			return 0;
		}

		int[] arrs = new int[1];
		pathSumIII2Helper(root, sum, arrs, new int[1000], 0);
		return arrs[0];
	}

	public void pathSumIII2Helper(TreeNode root, int sum, int[] arrs, int[] path, int h) {
		if (root == null) {
			return;
		}
		path[h] = root.val;
		int sumPath = 0;
		for (int i = h; i >= 0; i--) {
			sumPath += path[i];
			if (sumPath == sum) {
				arrs[0]++;
			}
		}
		pathSumIII2Helper(root.left, sum, arrs, path, h + 1);
		pathSumIII2Helper(root.right, sum, arrs, path, h + 1);
	}


	//129. 求根到叶子节点数字之和
	public int sumNumbers(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int[] result = new int[1];
		sumNumbersHelper(root, 0, result, 0);
		return result[0];
	}

	public void sumNumbersHelper(TreeNode root, int preSum, int[] ints, int h) {
		if (root == null) {
			return;
		}
		//记录每一层的结果
		int nSum = preSum * 10 + root.val;
		if (root.left == null && root.right == null) {
			ints[0] += nSum;
		}
		sumNumbersHelper(root.left, nSum, ints, h + 1);
		sumNumbersHelper(root.right, nSum, ints, h + 1);
	}

	//543. 二叉树的直径
	public int diameterOfBinaryTree(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int[] result = new int[1];
		result[0] = 1;
		diameterOfBinaryTreeHelper(root, result);
		return result[0] - 1;
	}

	public int diameterOfBinaryTreeHelper(TreeNode root, int[] result) {
		if (root == null) {
			return 0;
		}
		int lDepth = diameterOfBinaryTreeHelper(root.left, result);
		int rDepth = diameterOfBinaryTreeHelper(root.right, result);
		result[0] = Math.max(lDepth + rDepth + 1, result[0]);
		return Math.max(lDepth, rDepth) + 1;
	}

	//687. 最长同值路径
	public int longestUnivaluePath(TreeNode root) {
		if (root == null) {
			return 0;
		}
		int[] result = new int[1];
		longestUnivaluePathHelper(root, result);
		return result[0];
	}

	public int longestUnivaluePathHelper(TreeNode root, int[] result) {
		if (root == null) {
			return 0;
		}

		int lPath = longestUnivaluePathHelper(root.left, result);
		int rPath = longestUnivaluePathHelper(root.right, result);
		int arrowLeft = 0, arrowRight = 0;
		if (root.left != null && root.left.val == root.val) {
			arrowLeft = lPath + 1;
		}
		if (root.right != null && root.right.val == root.val) {
			arrowRight = rPath + 1;
		}
		result[0] = Math.max(result[0], arrowLeft + arrowRight);
		return Math.max(arrowLeft, arrowRight);
	}

	//

	public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
		parent = new HashMap();
		dfs(root, null);

		Queue<TreeNode> queue = new LinkedList();
		queue.add(null);
		queue.add(target);

		Set<TreeNode> seen = new HashSet();
		seen.add(target);
		seen.add(null);

		int dist = 0;
		while (!queue.isEmpty()) {
			TreeNode node = queue.poll();
			if (node == null) {
				if (dist == K) {
					List<Integer> ans = new ArrayList();
					for (TreeNode n : queue)
						ans.add(n.val);
					return ans;
				}
				queue.offer(null);
				dist++;
			} else {
				if (!seen.contains(node.left)) {
					seen.add(node.left);
					queue.offer(node.left);
				}
				if (!seen.contains(node.right)) {
					seen.add(node.right);
					queue.offer(node.right);
				}
				TreeNode par = parent.get(node);
				if (!seen.contains(par)) {
					seen.add(par);
					queue.offer(par);
				}
			}
		}

		return new ArrayList<Integer>();
	}

	public void dfs(TreeNode node, TreeNode par) {
		if (node != null) {
			parent.put(node, par);
			dfs(node.left, node);
			dfs(node.right, node);
		}
	}
}